Entities (e.g., companies, individuals, systems, etc.) may store large amounts of information. In some cases, entities may have data sources which are interconnected between other entities. For example, one company may have a database that is shared with another company. In some cases, the shared database may include a shared and replicated database which means that the database is not a single database but rather a database that is replicated and shared between the entities connected on a network.
To ensure that the data match across all replicated instances, the fingerprint or signature of the information within the database needs to be computed. One method of computing a fingerprint or signature is to compute a crypto-hash associated with the information. For efficient computation of the fingerprint or signature, the information within the database is typically organized in a hierarchical data structure. One type of hierarchical data structure is a Merkle tree. In a hierarchical data structure, information is organized within nodes. When a single node changes, the fingerprint for this node is recomputed. Additionally, because the fingerprint of one node changed, the fingerprint of other nodes, including the root node, need to be recomputed.